﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0076_SubsetsWithDup : IAlgorithm
    {
        // 90. 子集 II

        // 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
        // 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

        // 提示：
        //  1 <= nums.length <= 10
        //  -10 <= nums[i] <= 10

        public void Test()
        {
            // 算法参数定义
            var nums = new int[] { 1, 2, 2 };
            // 算法执行与打印
            var res = SubsetsWithDup(nums);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        public IList<IList<int>> SubsetsWithDup(int[] nums)
        {
            var numsList = nums.ToList();
            numsList.Sort();
            List<IList<int>> res = new List<IList<int>>();
            Backtrack(0, numsList.ToArray(), res, new List<int>());
            return res;
        }
        private void Backtrack(int i, int[] nums, List<IList<int>> res, List<int> tmp)
        {
            res.Add(tmp.ToArray());
            for (int j = i; j < nums.Length; j++)
            {
                if (j > i && nums[j] == nums[j - 1])
                    continue;
                tmp.Add(nums[j]);
                Backtrack(j + 1, nums, res, tmp);
                tmp.RemoveAt(tmp.Count - 1);
            }
        }
    }
}
